import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 394. Decode String 字符串解码
 * https://leetcode.com/problems/decode-string/
 */
class DecodeString {
    /**
     * 方法：使用双栈法解码字符串。一个栈存储数字，另一个栈存储字符串。遇到数字时累积计算，遇到'['时将当前字符串和数字入栈，遇到']'时弹出数字和字符串进行重复拼接。
     * 
     * Args:
     *   s: 需要解码的字符串
     * 
     * Returns:
     *   String: 解码后的字符串
     * 
     * Time: O(n) - 需要遍历整个字符串
     * Space: O(n) - 最坏情况下栈的大小为n/2
     */
    public String decodeString(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<String> strStack = new ArrayDeque<>();
        StringBuilder curStr = new StringBuilder();
        int curNum = 0;
        for(Character c : s.toCharArray()){
            if(Character.isDigit(c)){
                curNum = curNum * 10 + (c - '0');
            } else if(c == '['){
                numStack.push(curNum);
                strStack.push(curStr.toString());
                curNum = 0;
                curStr = new StringBuilder();
            } else if(c == ']'){
                int num = numStack.pop();
                StringBuilder temp = new StringBuilder(strStack.pop());
                for(int i = 0; i < num; i++){
                    temp.append(curStr);
                }
                curStr = temp;
            } else {
                curStr.append(c);
            }
        }
        return curStr.toString();
    }
}